1. Field of the Invention
The present invention relates to a minimum distance storing device for storing obtained minimum distances by arranging them in ascending order (or in descending order of similarity).
2. Description of the Background Art
A conventional pattern recognition method used for recognition of patterns in speech data and character data is such as to store an unknown input pattern and a plurality of known standard patterns obtained by the same manner that the unknown pattern is obtained, determine distance values (or similarity values) between the unknown pattern and every known pattern, select a plurality of standard patterns that have smaller distance values (or higher similarity values), store the patterns in a result memory after arranging them in the ascending order (or in the descending order of similarity) and then specify the unknown input pattern according to the plurality of the stored distance values (or similarity values) in the result memory.
As described above, the conventional pattern recognition stores the data in the result memory in the ascending distance-value order or in the descending similarity order, but both orders are generally the same relationship in tens of being sequential. Accordingly, a case when N pieces of resultant data are stored in the ascending order will be, by way of example, described as follows:
A sort algorithm is a known method for arranging N pieces of distances in the ascending order. The representative process for arranging distances is performed in the ascending order.
To store N pieces of distance values in ascending order, a result memory must have N pieces of memory areas from address (0) to address (N-1)!. The results of performed algorithm are recorded in the addresses 0 to (N-1) of the result memory.
Namely, a content A of the leading address (I=0) of the result memory is first read, an address (J=I+1) adjoining to the leading address is determined and then a content B of the result memory, which is designated by address J, is read out.
Both the contents A and B are compared with each other. If A is smaller than B (i.e., A&lt;B), no operation is performed other than a jump to the next step. If A.gtoreq.B, this step replaces A and B with each other and proceeds to the next step. In other words, this step causes A to be a content of the memory area addressed by (J) and B to be a content of the memory area addressed by (I).
The next step updates the address (I) and repeats the similar processing operation. This cycle is repeated by (N-1) times to move a maximal value stored in one of the addresses (0) to (N-1) into the memory area specified by the address (N-1).
Processing addresses of the result memory are then changed to the addresses (0) to (N-2) and a processing cycle similar to the above-mentioned cycle is repeated by (N-2) times to store the maximal value among the addresses (0) to (N-2) in the memory address (N-2).
The processing steps are repeatedly performed until the result memory address reaches the address (0), i.e., by further performing steps (n-3), (n-4) . . . (0). The distance values are stored in the ascending order in the result memory.
In regard to the number of memory accesses which may vary depending on the branch conditions, the above-mentioned processing may access the memory in a shortest path: ##EQU1## and in a longest path: ##EQU2##
In the above-mentioned conventional example, the number of memory accesses is an important factor that may have a great influence on a processing time. The less the number of accesses is, the shorter the processing time is. The above-mentioned conventional process, however, must access the same addresses each several times (e.g., address (0) by (N-1) times, address (1) by (N-2) . . . ), that may prolong the processing time.
Hardware necessary for realizing the above-mentioned processing must include a system for generating adjoining addresses and a multiloop control system and, therefore, may be large and complicated.
The application of the above-described algorithm without modification is not practical because the pattern recognition requires a large number of reference patterns. The number of reference patterns, therefore, must be reduced to the minimum required.
In other words, in every calculation of a distance between an input pattern and a reference pattern, a maximum value is determined among N pieces of stored values and is replaced with the calculation result if it is larger than the calculation result. As a result of this, N pieces of minimum distance values are randomly stored.
The minimum-distance memory (for storing distance values in the ascending order) in the pattern recognition involves another problem to be considered. This relates to how to process the same category data.
Usually, a plurality of standard patterns for the same category may be prepared for pattern recognition. Accordingly, the minimum-distance memory adopts the minimal distance-value in the same category as a representative of the category.
Namely, besides the above-mentioned distance-value relation, the distance-value relation in the same category must be also regarded. For the category processing, the conventional processing method requires more processing time and its hardware may be more increased in size and more complicated in structure.